#include <stdio.h>
#include <stdlib.h>

int min(int *a, int n)
{
	int min = 0;
	for(int i = 0;i < n; i++)
	{
		if(a[i] < a[min])
		{
			min = i;
		}
	}
	return a[min];
}

int max(int *a, int n)
{
	int max = 0;
	for(int i = 0;i < n; i++)
	{
		if(a[i] > a[max])
		{
			max = i;
		}
	}
	return a[max];
}

void SelectionSort(int *a, int n)
{
	int min, tmp;
	for(int i = 0; i < n-1; i++)
	{
		min = i;
		for(int j = i+1; j < n; j++)
		{
			if(a[j] < a[min])
			{
				min = j;
			}
		}
		tmp = a[i];
		a[i] = a[min];
		a[min] = tmp;
		printf("第%d轮排序数据：");
		for(int k = 0; k < n; k ++)
		{
			printf("%d ", a[k]);
		}
		printf("\n");
	}
}
/*
使用1：
		bucket[i] = (int*)malloc(sizeof(int));
		bucketIn = (int*)realloc(bucket[i], sizeof(int));
使用2：
	for(int i = 0; i < 3; i++)
	{
		bucket[i] = (int*)malloc(sizeof(int));
		printf("%d\n", bucket[i]);
	}
	for(int i = 0; i < 3; i++)
	{
		bucketIn[i] = (int*)realloc(bucket[i], sizeof(int));
		printf("%d\n", bucket[i]);
	}
*/
void BucketSort(int *a, int n)
{
	int minV, maxV;
	int bucketCount, perBucket, bucketIndex;
	int count = 0;
	int *bucket[3];
	int bucketValueNum[3] = {0,0,0};
	
	minV = min(a, n);
	maxV = max(a, n);
	bucketCount = 3;
	perBucket = (maxV - minV + bucketCount) / bucketCount;
	
	printf("bucket[3]初识地址内存分配：");
	for(int i = 0; i < 3; i++)
	{
		bucket[i] = (int*)malloc(sizeof(int));
		printf("%d  ", bucket[i]);
	}
	printf("\n");
	
	for(int i=0;i < n; i++)
	{
		bucketIndex = (a[i] - minV) / perBucket;
		bucketValueNum[bucketIndex]++;
		//bucket[bucketIndex] = (int*)malloc(sizeof(int));
		printf("重分配内存前地址：%d\n", bucket[bucketIndex]);
		bucket[bucketIndex] = (int*)realloc(bucket[bucketIndex], bucketValueNum[bucketIndex] * sizeof(int));
		printf("重分配内存后地址：%d\n", bucket[bucketIndex]);
		printf("重分配后地址上数据：%d\n", *bucket[bucketIndex]);
		*(bucket[bucketIndex] + bucketValueNum[bucketIndex] - 1) = a[i];
		
		printf("第%d次%d桶内新增元素：%d\n", i, bucketIndex, a[i]);
		printf("同上：%d\n", *(bucket[bucketIndex] + bucketValueNum[bucketIndex] - 1));
		printf("桶内元素个数：%d\n", bucketValueNum[bucketIndex]);
		printf("桶内元素：");
		for(int j=0; j < bucketValueNum[bucketIndex]; j++)
		{
			printf("%d ", *(bucket[bucketIndex] + j));
		}
		printf("\n\n");
	}

	for(int k =0; k < bucketCount; k++)
	{
		printf("%d\n",bucket[k]);
		SelectionSort(bucket[k], bucketValueNum[k]);
	}

	int idx = 0;
	printf("函数内排序数组：");
	for(int k =0; k < bucketCount; k++)
	{
		for(int t=0; t < bucketValueNum[k]; t++)
		{
			a[idx] = *(bucket[k] + t);
			printf("%d ", a[idx]);
			idx++;
		}
	}
	printf("\n");
	
	free(bucket[0]);
	free(bucket[1]);
	free(bucket[2]);
}

int main()
{
   /*  Write C code in this online editor and run it. */
    int a[8] = {8,7,6,5,4,3,2,1};
	int n = sizeof(a)/sizeof(int);
	
	printf("原始序列：");
	for(int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	
	BucketSort(a, n);
	
	printf("排序序列：");
	for(int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
   
   return 0;
}

/*
原始序列：8 7 6 5 4 3 2 1 
bucket[3]初识地址内存分配：6374000  6374032  6374064  
重分配内存前地址：6374064
重分配内存后地址：6374064
重分配后地址上数据：0
第0次2桶内新增元素：8
同上：8
桶内元素个数：1
桶内元素：8 

重分配内存前地址：6374064
重分配内存后地址：6374064
重分配后地址上数据：8
第1次2桶内新增元素：7
同上：7
桶内元素个数：2
桶内元素：8 7 

重分配内存前地址：6374032
重分配内存后地址：6374032
重分配后地址上数据：0
第2次1桶内新增元素：6
同上：6
桶内元素个数：1
桶内元素：6 

重分配内存前地址：6374032
重分配内存后地址：6374032
重分配后地址上数据：6
第3次1桶内新增元素：5
同上：5
桶内元素个数：2
桶内元素：6 5 

重分配内存前地址：6374032
重分配内存后地址：6374032
重分配后地址上数据：6
第4次1桶内新增元素：4
同上：4
桶内元素个数：3
桶内元素：6 5 4 

重分配内存前地址：6374000
重分配内存后地址：6374000
重分配后地址上数据：0
第5次0桶内新增元素：3
同上：3
桶内元素个数：1
桶内元素：3 

重分配内存前地址：6374000
重分配内存后地址：6374000
重分配后地址上数据：3
第6次0桶内新增元素：2
同上：2
桶内元素个数：2
桶内元素：3 2 

重分配内存前地址：6374000
重分配内存后地址：6374000
重分配后地址上数据：3
第7次0桶内新增元素：1
同上：1
桶内元素个数：3
桶内元素：3 2 1 

6374000
第3轮排序数据：1 2 3 
第10轮排序数据：1 2 3 
6374032
第3轮排序数据：4 5 6 
第10轮排序数据：4 5 6 
6374064
第2轮排序数据：7 8 
函数内排序数组：1 2 3 4 5 6 7 8 
排序序列：1 2 3 4 5 6 7 8 
/